package Intermediate_algorithm.Backtracking;

import org.junit.Test;

import java.security.Key;
import java.util.*;

/*
电话号码的字母组合
给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]

提示：
0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。
相关标签
Java
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/top-interview-questions-medium/xv8ka1/
 */
public class _01电话号码的字母组合 {

    @Test
    public void test() {
        System.out.println(letterCombinations("23"));
    }

    //BFS + 模拟
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return res;
        }
        Map<Character,List<Character>> map = new HashMap(){{
            put('2',Arrays.asList('a','b','c'));
            put('3',Arrays.asList('d','e','f'));
            put('4',Arrays.asList('g','h','i')) ;
            put('5',Arrays.asList('j','k','l')) ;
            put('6',Arrays.asList('m','n','o')) ;
            put('7',Arrays.asList('p','q','r','s'));
            put('8',Arrays.asList('t','u','v'));
            put('9',Arrays.asList('w','x','y','z'));
        }};
        Queue<StringBuilder> queue = new LinkedList<>();
        char key = digits.charAt(0);
        List<Character> list = map.get(key);
        for (int i = 0; i < list.size(); i++) {
            queue.offer(new StringBuilder().append(list.get(i)));
        }
        if(digits.length() == 1){
            while (!queue.isEmpty()) {
                res.add(queue.poll().toString());
            }
            return res;
        }
        for (int i = 1; i < digits.length(); i++) {
            char index = digits.charAt(i);
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                StringBuilder s = queue.poll();
                List<Character> characters = map.get(index);
                for (int k = 0; k < characters.size(); k++) {
                    Character c = characters.get(k);
                    s.append(c);
                    queue.offer(new StringBuilder(s.toString()));
                    if(i == digits.length()-1){
                        res.add(s.toString());
                    }
                    s.deleteCharAt(s.length() - 1);
                }
            }
        }
        return res;
    }

    //他人解法
    //优化直接采用String拼接
    public List<String> letterCombinations2(String digits) {
        List<String> result = new ArrayList<>();
        int n = digits.length();
        if (n == 0){
            return result;
        }
        Map<Character, List<String>> map = new HashMap<>();
        map.put('2', Arrays.asList("a","b","c"));
        map.put('3', Arrays.asList("d","e","f"));
        map.put('4', Arrays.asList("g","h","i"));
        map.put('5', Arrays.asList("j","k","l"));
        map.put('6', Arrays.asList("m","n","o"));
        map.put('7', Arrays.asList("p","q","r","s"));
        map.put('8', Arrays.asList("t","u","v"));
        map.put('9', Arrays.asList("w","x","y","z"));
        result = map.get(digits.charAt(0));
        if (n == 1){
            return result;
        }
        int i = 1;
        while (i < n){
            List<String> temp = new ArrayList<>();
            for (String s1 : result) {
                for (String s2 : map.get(digits.charAt(i))) {
                    temp.add(s1+s2);
                }
            }
            result = temp;
            i++;
        }
        return result;
    }

    //官解：方法一：回溯
    //看起来像DFS
    /*
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/solutions/388738/dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode-solutio/
     */
    class Solution {
        public List<String> letterCombinations(String digits) {
            List<String> combinations = new ArrayList<String>();
            if (digits.length() == 0) {
                return combinations;
            }
            Map<Character, String> phoneMap = new HashMap<Character, String>() {{
                put('2', "abc");
                put('3', "def");
                put('4', "ghi");
                put('5', "jkl");
                put('6', "mno");
                put('7', "pqrs");
                put('8', "tuv");
                put('9', "wxyz");
            }};
            backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
            return combinations;
        }

        public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
            if (index == digits.length()) {
                combinations.add(combination.toString());
            } else {
                char digit = digits.charAt(index);
                String letters = phoneMap.get(digit);
                int lettersCount = letters.length();
                for (int i = 0; i < lettersCount; i++) {
                    combination.append(letters.charAt(i));
                    backtrack(combinations, phoneMap, digits, index + 1, combination);
                    combination.deleteCharAt(index);
                }
            }
        }
    }

}
